1463D - Pairs - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define en '\n'
#define vec vector
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define in(x,y) (y).find((x))!=(y).end()
#define nin(x,y) (y).find((x))==(y).end()

#ifdef DEBUG
#include "template/debug.h"
#else
#define debug(x...)
#endif 

void solve() {
	int n; cin>>n;
	vec<int> black(2*n+1);
	map<int, int> mp;
	int bd1=0;
	for(int i=1; i<=n; ++i){
		int x; cin>>x;
		mp[i]=x;
		black[x]=1;
		if(x==i){
			++bd1;
		}
	}
	debug(n, black);
	int a=0, b=0;
	for(int i=2*n; i>=1; --i){
		if(!black[i]){
			++b;
			if (a>0){
				--b;
				--a;
			}
		} else {
			++a;
		}
	}
	int bd2=mp[b];
	int lb=max(bd1, bd2);
	int l=lb, r=2*n;
	//debug(l, r);
	while(l<r){
		int m=l+(r-l+1)/2;
		debug(m);
		bool ok=true;
		deque<int> ninb;
		for(int i=1; i<=2*n; ++i){
			if(!black[i]){
				ninb.pb(i);
			}
		}
		debug(ninb);
		for(int i=2*n; i>=1; --i){
			if(black[i]){
				if(i<=m){
					int x=ninb.back();
					ninb.pop_back();
					if(x<i){
						ok=false; break;
					}
				} else {
					int x=ninb.front();
					ninb.pop_front();
					if(x>i){
						ok=false; break;
					}
				}
			}
		}
		if(ok) l=m;
		else r=m-1;
	}
	debug(lb, l);
	int res=0;
	for(int i=lb; i<=l; ++i){
		if(black[i]){
			++res;
		}
	}
	if(lb==0)++res;
	cout<<res<<en;
}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t=1;
	cin>>t;
	while(t--) solve();
}